1. Field of the Invention
The present invention relates to the data structure of a high-speed retrievable table, especially to an information apparatus with a table that can realize the longest prefix match search at high speed and that can also perform processes at high speed such as the retrieval and preparation of a table, or the addition, modification, and deletion of table items.
2. Description of the Related Art
A process of storing a plurality of pieces of data in the array (table) that has a specific structure, and retrieving data that matches particular data is used in many areas in an information process. Among the areas, for example, the longest prefix match search is used for the longest prefix match search of a dictionary or for the retrieval of a path table that is used for a routing process in the Internet protocol, and accordingly the search is important.
The representative application example that requires the longest prefix match search is the path table retrieval that is used for the Internet protocol, etc.
The following explanation is of a case of the path table retrieval. The longest prefix match search, however, can be used for various types of usage including a database retrieval, etc., and accordingly it is not limited to the path table retrieval.
In the following explanation, furthermore, a network address of 32 bits of IPv4 is divided into, for example, “aaa. bbb. ccc. ddd” for each 8 bits, and each 8-bit value is expressed with decimal notation. For example, “10.0.0.1” is “0x0A000001” if expressed in hexadecimal notation. Also, the length of a network unit is explicitly expressed as, for example, “10.0.0.0/24”. This indicates that the network unit of 10.0.0.0 is 24 bits (10.0.0) from the top. These notations are generally accepted. In the following explanation, a value for which specific designation is not required (don't care), is indicated by an “x” such in, for example, “10.0.0.x”.
A path table is a database arranging network address and path information to reach a network address in a pair. When an Internet router receives a packet from the network, it retrieves a path table setting the destination address of this packet as retrieval data, detects the longest matching network address, and transfers the packet toward the path of the network address. Here, the path is the next link forwarding the packet.
FIG. 1 shows one example of a path table.
For example, assume that a network address and path like FIG. 1 are registered in the path table.
In this example, when “10.0.1.2” is given as retrieval data (destination of packet), “10.0.1.0” is matched. This is because “10.0.1.0” is matched as being one bit longer than “10.0.1.128”, taking a bit unit into consideration. In the case that the entry of “10.0.1.0” is not present in a path table, “10.0.1.128” becomes the longest prefix match. If “10.0.1.128” is not present, “10.0.0.0” becomes the longest prefix match; if “10.0.0.0” is not present, “10.1.0.0” becomes the longest prefix match; and if “10.1.0.0” is not present, “0.0.0.0” becomes the longest prefix match. In the case that “0.0.0.0” becomes the longest prefix match, the upper 4 bits match with “0”.
Furthermore, there is a concept called a default route in a routing process. Even in the case that there is not a matching path in retrieval data, a used path can be defined, so that the retrieval process of a path table can be successful and does not fail.
The object when attempting the longest prefix match search is to minimize the processes of retrieving a table, adding a table, modifying a table, deleting a table, etc., and to perform these processes at high speed. As for conventional technologies, there are many methods such as a method devising retrieval algorithm (articles 1˜6), a method using a hardware CAM (Contents Addressable Memory) (articles 1˜8), and a new method (articles 9 and 10). Most of these methods aim at a path table retrieval. However, the longest prefix match search of these methods remains at the same level as a word retrieval.
The retrieval of a path table is originally realized by software. Fundamentally, a retrieval method using Binary Tree and also Radix Tree has been used. However, a packet is transmitted at a speed of hundreds of thousands of packets/second in a high-speed network. Therefore, software cannot cope with such high-speed transmission. In the case that a path table is retrieved in a time less than a microsecond, a hardware retrieval method is used. In hardware retrieval, generally, a path table is controlled by software, and hardware is optimized so as to process retrieval at high speed. The Tiny Tera method (article 11) developed by Stanford University is a representative example of such a retrieval method.
FIG. 2 is a diagram explaining the Tiny Tera method.
The Tiny Tera method performs a path table retrieval process as follows:                A retrieval key is divided into two fields.        When a length of the retrieval key is K, the first field is P, and the second field is K-P.        In the case of IPv4 (Internet Protocol version 4: K=32), P=24.        A table (first retrieval table) for looking up the first field as an index is provided.        A pointer to path information or the second retrieval table is stored in the first retrieval table.        The second retrieval table prepares the required number of tables of 2k-P entries.        The first retrieval table is retrieved by the first field (Step 1).        If path information is obtained, it becomes the result (the first result).        If a pointer to the second retrieval table is obtained, the second retrieval table is retrieved by this pointer and the second field (step 2).        
In this way, the retrieval process terminates with two accesses at most in the Tiny Tera method.
In the Tiny Tera method, a path retrieval of the IPv4 address terminates by accessing a table twice at most. As it is clear from the method, the retrieval process can be easily performed by hardware. In this case, it is possible to make the retrieval time equal to or less than 100 ns. However, there are the following problems:                As the first retrieval table, a memory for 224 (approx. 16,000,000 bytes) entries is required.        The number of paths that are used in the present Internet is 100,000 at maximum, and accordingly the first retrieval table becomes thin since only {fraction (1/160)} of the table is used (in other words, the memory is not fully used).        Since a table of 16 M words generally does not enter into a cache memory, cache errors frequently occur. Accordingly, a path table needs to be accessed each time there is a cache error, resulting in deterioration of the processing speed.        In the Tiny Tera method, basically, a network path is developed to a host path. Therefore, for example, when a network of which the network address is 8 bits, is registered in the first retrieval table, 216 (about 65,000) entries are required to be developed into a table and the same path information is provided with all these entries. In other words, only 8 bits are used for the value responded by 24 bits that is a retrieval key of the first retrieval table. Therefore, path information is registered for all the values that the remaining 16 bits can assume.        A time proportional to the number of entries is required at the time of preparation, modification, deletion of a path table.        Since all the entries cannot be modified at one time, an inconsistent data condition occurs during modification. Therefore, there is the possibility that the inconsistent data is obtained in the longest prefix match search that is carried out at this time.        The method cannot cope with a network protocol that has a long address such as IPv6 (Internet Protocol version 6). In other words, the number of entries to be registered greatly increases when a network address becomes long. Accordingly, the above-mentioned problem becomes more serious.        
FIG. 3 is a drawing showing the concept of the routing process of a router.
A router R needs to transfer packets to networks N1 to N4 connected to the router R. At this time, a destination address of the packet that is input to the router R is checked, and it is determined to which path the packet is transmitted. At this time, generally, a plurality of different networks N1 to N4 are connected to the router R. In this case, different paths are not allocated to all the networks. As shown in FIG. 3, for example, a packet is often transmitted to the networks N1 and N4 using the same path l1 connected to one port of the router R. In such a case, since all the packets of which the addresses are the networks N1 and N4, are output to the path l1, l1 is registered in the path table as an output path of both the network addresses N1 and N4.
FIG. 4 shows the concept of a path table of the Tiny Tera method.
In the case of FIG. 4, the network address N1 is made shorter than 24 bits. In this case, entries are formed for all the bit values that are added behind the network, among 24 bits. l1 is registered as an output path for all the paths. If it is assumed that the network address N4 is longer than 24 bits and consists of bit values V4 and W4, the first path table is first retrieved by the bit value V4 of 24 bits in a table (1) of FIG. 4. Then, since a pointer to the second route table is acquired, based on this pointer, a path table (2) of FIG. 4 is retrieved by the bit value W4. Thus, 14 is acquired as an output path. Further, if it is assumed that a network address N3 consists of just 24 bits, 13 is acquired as an output path since there is only one entry of the network address N3.
The path table does not perform a comparing/matching process of a network address obtained by a network address storage unit and a network address obtained by a packet, but the path table is directly referred to while setting the network address obtained by a packet as an offset. Therefore, for all the values that the network address can assume, a memory area must be provided even if such an address is not present. Accordingly, even if the register number of network addresses registered in the path table is less than 224, the first path table requires a memory capacity of 224 entries. In other words, there is the problem that a memory area that is not used is present, and many memory capacities are rapidly required when the number of bits of a key for retrieving the path table increases as the number of bits of the network address increases.